package company;

public class    SingleLinkedList {
    private int size;
    private Node head;

    public void addFirst(int val)  //头插法
    {
        Node node = new Node(val);
        if (head == null) {
            head = node;
        } else {
            node.next = head;  //完成节点的转移
            head = node;
        }
        size++; //每添加一个数据，空间加一
    }

    public void addIndex(int index, int val) //任意位置插入
    {
        if (index < 0 || index > size) {
            System.out.println("add index illgeal!");
            return;
        }
        if (index == 0) //插入节点作为了头结点
        {
            addFirst(val);
            return;
        }
        Node node = new Node(val);//需要插入的节点以及内容
        Node prev = head;
        for (int i = 0; i < index - 1; i++) //找到插入位置的前驱节点的索引
        {
            prev = prev.next;
        }
        node.next = prev.next; //
        prev.next = node;
        size++;
    }

    public void addLst(int val)//尾插法
    {
        addIndex(size, val);//索引到size-1处，在其后添加元素
    }

    public int get(int index)//根据索引获取对应值
    {
        if (rangCheck (index)) {
            Node node = head;
            for (int i = 0; i < index; i++) //遍历到前驱节点
                node = node.next;
            return node.val;
        } else {
            System.err.println("get index illegal!");
            return -1;
        }
    }

    public boolean contains(int val)//判断链表内是否存在值为val的数
    {
        for (Node temp = head; temp != null; temp = temp.next) {
            if (temp.val == val) {
                return true;
            }
        }
        return false;
    }
    //将索引位置的val改为newVal,然后返回修改前的值
    public int set(int index,int newVal)
    {
        if(rangCheck(index))
        {
            Node node =head;
            for(int i=0;i<index-1;i++)
            {
                node=node.next;
            }
            int oldVal=node.val;
            node.val=newVal;
            return oldVal;
        }
        else
        {
            System.err.println("set index illgal!");
            return -1;
        }
    }
//删除索引位置的节点
    public void removeIndex(int index)
    {
        if(rangCheck(index))
        {
            if(index==0) {//删除节点为头结点，且还有其它节点
                Node temp = head;  //引用，替代头结点，防止头结点丢失
                head = head.next;
                temp.next=null;
                size--;
            }
            else
            {
                Node prev=head;
                for(int i=0;i<index-1;i++)
                {
                    prev=prev.next;
                }
                Node cur=prev.next;//先断的话找不到cur，next的地址
                prev.next=cur.next;
                cur.next=null;
                size--;
            }

        }
        else{
            System.err.println("remove index illegal!");
        }
    }
    public void removeFirst()
    {
        removeIndex(0);
    }
    public void removeLast()
    {
        removeIndex(size-1);
    }
    //找到数值为val的数，并且删除（不知道索引位置）
    public void removeValueOnce(int val) {
        if (head != null && head.val == val) {
            removeFirst();
        } else {
            Node prev = head;
            while (prev.next!= null)
            {
                if(prev.next.val==val)
                {
                    Node cur=prev.next;
                    prev.next=cur.next;
                    cur.next=null;
                    size--;
                }
            }
        }
    }
    //删除所有值为val的节点
    public void removeValueAll(int val)
    {
        while(head!=null&&head.val==val)//如果头结点不为空且每次循环的头结点都是val，全部删除

        {//即整个链表的所有节点值都为val
            head=head.next;
            size--;
        }
        if(head==null)//链表全部删除
            return ;
        else
        {
            Node prev=head;
            while(prev.next!=null)
            {
                if(prev.next.val==val)//找前驱节点
                {
                    Node cur=prev.next;
                    prev.next=cur.next;
                    cur.next=null;
                    size--;
                }
                else
                {
                    prev=prev.next;
                }
            }
        }
    }



//合法性判断封装
        public boolean rangCheck (int index)
        {
            if (index < 0 || index > size) {
                return false;
            }
            return true;
        }


        public String toString ()  //打印成员方法
        {
            String ret = "";
            Node node = head;
            while (node != null) {
                ret += node.val;
                ret += "->";
                node = node.next;
            }
            ret += "NULL";
            return ret;
        }
}
